//给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 
//
// 测试用例的答案是一个 32-位 整数。 
//
// 子数组 是数组的连续子序列。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [2,3,-2,4]
//输出: 6
//解释: 子数组 [2,3] 有最大乘积 6。
// 
//
// 示例 2: 
//
// 
//输入: nums = [-2,0,-1]
//输出: 0
//解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。 
//
// 
//
// 提示: 
//
// 
// 1 <= nums.length <= 2 * 10⁴ 
// -10 <= nums[i] <= 10 
// nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数 
// 
//
// Related Topics 数组 动态规划 👍 2174 👎 0

package leetcode.editor.cn;
//java:乘积最大子数组
public class Q0152MaximumProductSubarray {
    public static void main(String[] args){
        Solution solution = new Q0152MaximumProductSubarray().new Solution();
        solution.maxProduct(new int[]{-4,-3,-2});
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxProduct(int[] nums) {
            int length = nums.length;
            int dpMax = nums[0], dpMin = nums[0], res = nums[0];

            for (int i = 1; i < length; i++) {
                // dpMin计算时需要dpMax， 需要先将dpMax的值保存一下
                int max = dpMax, min = dpMin;
                dpMax = Math.max(max * nums[i], Math.max(min * nums[i], nums[i]));
                // 当nums[i] < 0， 需要dpMin 越小越好，为负数的话。当 > 0 需要 dpMax 越大越好
                dpMin = Math.min(max * nums[i], Math.min(min * nums[i], nums[i]));
                res = Math.max(res, dpMax);
            }
            return res;
        }
    }

//leetcode submit region end(Prohibit modification and deletion)

}